//
// Created by lyc on 2025/2/28.
// 递归, 背包问题
// 大致思路就是利用递归去遍历所有可能的情况，最终选出最好那一种
//
#include "iostream"
#include "vector"
#include "map"
#include "algorithm"
using namespace std;
double packVolumn;

// first: weight, second: Value
vector<pair<double, double>> objVector;


double RecurTry(int index, double currWeight, vector<pair<double, double>>& objVector){
    /**
     * func: 自我递归函数, 目的是遍历所有可能的情况, 当容量不足或者所有物品遍历完后, 返回。
     *       对于每个物品, 有两种情况, 1 装入背包  2 不装入
     * param: 当前背包被占用重量, 当前背包内价值, 该物品重量, 该物品价值
     * return: void
     */
    if(index >= objVector.size()){
        return 0;
    }


    double objWeight = objVector[index].first;
    double objValue = objVector[index].second;

    // 不选择该物品
    double value1 = RecurTry(index + 1, currWeight, objVector);


    // 选择该物品
    double value2 = 0;
    if(currWeight + objWeight <= packVolumn){
        value2 = RecurTry(index + 1, currWeight + objWeight, objVector) + objValue;
    }

    return max(value1, value2);

}

void algorithm8(){
    cout << "Enter the number of Objects" << endl;
    int number;
    cin >> number;

    cout << "Enter param of obj" << endl;
    double weight, value;
    for(int i = 0; i < number; i++){
        cin >> weight >> value;
        objVector.push_back({weight, value});
    }

    cout << "Enter the Volumn of backPack" << endl;
    cin >> packVolumn;


    double bestValue = RecurTry(0, 0, objVector);

    cout << "the best Value: " << bestValue << endl;
}


